Sorting a Linked List [closed]
Posted
by
Mohit Sehgal
on Programmers
See other posts from Programmers
or by Mohit Sehgal
Published on 2012-11-14T11:11:41Z
Indexed on
2012/11/14
11:17 UTC
Read the original article
Hit count: 320
I want to sort a linked list. Here Node is class representing a node in a Linked List I have written a code to bubble sort a linked list. Program does not finishes execution. Kindly point out the mistakes.
class Node
{
public:
int data;
public:
Node *next;
Node()
{
data=0;next=0;
}
Node(int d)
{
data=d;
}
void setData(int d)
{
data=d;
}
void print()
{
cout<<data<<endl;
}
bool operator==(Node n)
{
return this->data==n.data;
}
bool operator >(Node d)
{
if((this->data) > (d.data))
return true;
return false;
}
};
class LList
{
public:
int noOfNodes;
Node *start;/*Header Node*/
LList()
{
start=new Node;
noOfNodes=0;start=0;
}
void addAtFront(Node* n)
{
n->next=(start);
start=n;
noOfNodes++;
}
void addAtLast(Node* n)
{
Node *cur=(start);
n->next=NULL;
if(start==NULL)
{
start=n;
noOfNodes++;
return;
}
while(cur->next!=NULL)
{
cur=cur->next;
}
cur->next=n;
noOfNodes++;
}
void addAtPos(Node *n,int pos)
{
if(pos==1)
{
addAtFront(n);return;
}
Node *cur=(start);
Node *prev=NULL;
int curPos=0;
n->next=NULL;
while(cur!=NULL)
{
curPos++;
if(pos==curPos+1)
{
prev=cur;
}
if(pos==curPos)
{
n->next=cur;
prev->next=n;
break;
}
cur=cur->next;
}
noOfNodes++;
}
void removeFirst()
{
Node *del=start;
start=start->next;
delete del;
noOfNodes--;
return;
}
void removeLast()
{
Node *cur=start,*prev=NULL;
while(cur->next!=NULL)
{
prev=cur;
cur=cur->next;
}
prev->next=NULL;
Node *del=cur->next;
delete del;
noOfNodes--;
return;
}
void removeNodeAt(int pos)
{
if(pos<1)
return;
if(pos==1)
{ removeFirst();return;}
int curPos=1;
Node* cur=start->next;
Node* prev=start;
Node* del=NULL;
while(curPos<pos&&cur!=NULL)
{
curPos++;
if(curPos==pos)
{
del=cur;
prev->next=cur->next;
cur->next=NULL;
delete del;
noOfNodes--;
break;
}
prev=prev->next;
cur=cur->next;
}
}
void removeNode(Node *d)
{
Node *cur=start;
if(*d==*cur)
{
removeFirst();return;
}
cur=start->next;
Node *prev=start,*del=NULL;
while(cur!=NULL)
{
if(*cur==*d)
{
del=cur;
prev->next=cur->next;
delete del;
noOfNodes--;
break;
}
prev=prev->next;
cur=cur->next;
}
}
int getPosition(Node data)
{
int pos=0;
Node *cur=(start);
while(cur!=NULL)
{
pos++;
if(*cur==data)
{
return pos;
}
cur=cur->next;
}
return -1;//not found
}
Node getNode(int pos)
{
if(pos<1)
return -1;// not a valid position
else if(pos>noOfNodes)
return -1; // not a valid position
Node *cur=(start);
int curPos=0;
while(cur!=NULL)
{
if(++curPos==pos)
return *cur;
cur=cur->next;
}
}
void reverseList()//reverse the list
{
Node* cur=start->next;
Node* d=NULL;
Node* prev=start;
while(cur!=NULL)
{
d=cur->next;
cur->next=start;
start=cur;
prev->next=d;
cur=d;
}
}
void sortBubble()
{
Node *i=start,*j=start,*prev=NULL,*temp=NULL,*after=NULL;
int count=noOfNodes-1;int icount=0;
while(i->next!=NULL)
{
j=start;
after=j->next;
icount=0;
while(++icount!=count)
{
if((*j)>(*after))
{
temp=after->next;
after->next=j;
prev->next=j->next;
j->next=temp;
prev=after;
after=j->next;
}
else{
prev=j;
j=after;
after=after->next; }
}
i=i->next;
count--;
}
}
void traverse()
{
Node *cur=(start);
int c=0;
while(cur!=NULL)
{
// cout<<"start"<<start;
c++;
cur->print();
cur=cur->next;
}
noOfNodes=c;
}
~LList()
{
delete start;
}
};
int main()
{
int n;
cin>>n;
int d;
LList list;
Node *node;
Node *temp=new Node(2123);
for(int i=0;i<n;i++)
{
cin>>d;
node=new Node(d);
list.addAtLast(node);
}
list.addAtPos(temp,1);
cout<<"traverse\n";
list.traverse();
temp=new Node(12);
list.removeNode(temp);
cout<<"12 removed";
list.traverse();
list.reverseList();
cout<<"\nreversed\n";
list.traverse();
cout<<"bubble sort\n";
list.sortBubble();
list.traverse();
getch();
delete node;
return 0;
}
© Programmers or respective owner
